package com.github.yangyishe.p100;

/**
 * 69. x 的平方根
 * https://leetcode.cn/problems/sqrtx/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 *
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 *
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 *
 * 提示：
 *
 * 0 <= x <= 231 - 1
 */
public class Problem69 {
    public static void main(String[] args) {
        int x=2147395599;

        Problem69 problem69 = new Problem69();
        int sqrt = problem69.mySqrt(x);
        System.out.println("sqrt = " + sqrt);
    }

    private static final int MAX_SQRT=46340;

    /**
     * 思路:
     * 将x看做一个长度为n的二进制数, 其平方根的长度大约为n/2.
     * 即, 确定一个n, 使2^n<=x<2^(n++1)
     *
     * 再之后, 使用二分查找, 查找出仅小于x的平方根.
     * 寻找方式为左闭右开
     *
     * @param x
     * @return
     */
    public int mySqrt(int x){
        // 遇到0提前返回
        if (x==0) {
            return 0;
        }

        //1. 确定n,即x的二进制位数.循环结束后,2^(n-1)<=x<2^n
        int n=0;
        int acc=1;
        while(acc<=x){
            acc=acc<<1;

            n++;
            //溢出处理
            if(n==31){
                break;
            }
        }
        // 2. 计算获取左右边界值
        int leftBit=(n-1)/2;
        int rightBit=leftBit+1;
        int left=1<<leftBit;
        int right=(1<<rightBit)+1;
        // 溢出情况考虑
        if(rightBit==16){
            right=MAX_SQRT;
            if(right*right<=x){
                return right;
            }
        }

        //2. 二分查找.左闭右开.即left^2<=x<right^2, 且left=right-1.
        // 如果遇到恰好相等的情况, 提前返回即可
        while(left<right-1){
            int mid=(left+right)/2;
            int res=mid*mid;
            if(res==x){
                return mid;
            }
            if(res<x){
                left=mid;
            }else{
                right=mid;
            }
        }

        return left;
    }
}
